import java.util.Stack;
class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minstack;
    public MinStack() {
        stack = new Stack<>();
        minstack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minstack.empty()){
            minstack.push(val);
        }else{
            if(val<=minstack.peek()){
                minstack.push(val);
            }
        }
    }

    public void pop() {
        if(stack.empty()){
            return;
        }
        int val = stack.pop();
        if(val == minstack.peek()){
            minstack.pop();
        }
    }

    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }

    public int getMin() {
        return minstack.peek();
    }
}
public class Text {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<tokens.length;i++){
            String str = tokens[i];
            if(isNumber(str)){
                stack.push(Integer.parseInt(str));
            }else{
                int nums1 = stack.pop();
                int nums2 = stack.pop();
                switch(str){
                    case "+":
                        stack.push(nums2+nums1);
                        break;
                    case "-":
                        stack.push(nums2-nums1);
                        break;
                    case "*":
                        stack.push(nums2*nums1);
                        break;
                    case "/":
                        stack.push(nums2/nums1);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isNumber(String str){
        if(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){
            return false;
        }
        return true;
    }
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(isleft(ch)){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char val = stack.peek();
                if(val == '(' && ch == ')' ||val == '[' && ch == ']' ||val == '{' && ch == '}' ){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.empty();
    }
    private boolean isleft(char ch){
        if(ch == ')' || ch == ']' || ch == '}'){
            return false;
        }
        return true;
    }
}
